﻿using System;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Problems.Sorting;
using Algoritmia.Utils;

namespace Algoritmia.Problems.CoinChange
{
    public class GreedyCoinChanger2 : IGreedyCoinChanger
    {
        private readonly ISorter<int> _sorter;
        private readonly IList<int> _list;

        public GreedyCoinChanger2(IList<int> list, Func<ISorter<int>> createSorter = null)
        {
            _list = list;
            createSorter = createSorter ?? (() => new BasicQuickSorter<int>());
            _sorter = createSorter();
        }

        #region Implementation of IGreedyCoinChanger

        public IList<int> Change( int Q)
        {
            var x = Enumerable.Repeat(0, _list.Count).ToAlgoritmiaList();
            foreach (var i in _sorter.Sorted(_list.Select((e, i) => i).ToAlgoritmiaList(), (i, j) => _list[j].CompareTo(_list[i])))
            {
                x[i] = Q / _list[i];
                Q = Q % _list[i];
                if ( Q == 0)
                {
                    return x;
                }
            }
            throw new InvalidOperationException("no solution was found");            
        }

        #endregion
    }
}
